package main

func (t *Tree) rbInsertFixup(z *node) {
	var y *node
	for z.parent != nil && z.parent.color == RED {
		//log.Info4("temp", "insert fixup p0", "z", z.Key)

		if z.parent == z.parent.parent.left {

			//log.Info4("temp", "insert fixup p1")

			y = z.parent.parent.right
			if y != nil && y.color == RED {
				z.parent.color = BLACK
				y.color = BLACK
				z.parent.parent.color = RED
				z = z.parent.parent
			} else {
				//log.Info4("temp", "insert fixup p2")

				if z == z.parent.right {
					z = z.parent

					//log.Info4("temp", "insert fixup left1")
					t.leftRotate(z)
				}
				z.parent.color = BLACK
				z.parent.parent.color = RED

				//log.Info4("temp", "insert fixup right1")
				t.rightRotate(z.parent.parent)
			}
		} else {
			//log.Info4("temp", "insert fixup p3")

			y = z.parent.parent.left
			if y != nil && y.color == RED {
				z.parent.color = BLACK
				y.color = BLACK
				z.parent.parent.color = RED
				z = z.parent.parent
			} else {
				if z == z.parent.left {
					z = z.parent

					//log.Info4("temp", "insert fixup right2")
					t.rightRotate(z)
				}
				z.parent.color = BLACK
				z.parent.parent.color = RED

				//log.Info4("temp", "insert fixup left2")
				t.leftRotate(z.parent.parent)
			}
		}
	}
	t.root.color = BLACK
}
